package com.bitauto.i.commonUtils.leet;

public class Answer4 {

    public static void main(String[] args) {
        int[] nums1 = new int[]{1};
        int[] nums2 = new int[]{3,4};
        double result1=findMedianSortedArrays1(nums1,nums2);
        System.out.println(result1);

        double result2=findMedianSortedArrays2(nums1,nums2);
        System.out.println(result2);
    }

    /**
     * 时间复杂度：遍历全部数组，O（m + n）
     * 空间复杂度：开辟了一个数组，保存合并后的两个数组，O（m + n）
     * @param nums1
     * @param nums2
     * @return
     */
    private static double findMedianSortedArrays1(int[] nums1, int[] nums2) {
        int[] nums;
        int m = nums1.length;
        int n = nums2.length;
        nums = new int[m + n];

        if(m==0){
            if(n%2==0){
                return (nums2[n/2-1]+nums2[n/2])/2;
            }else{
                return nums2[(n-1)/2];
            }
        }

        if(n==0){
            if(m%2==0){
                return (nums2[m/2-1]+nums2[m/2])/2;
            }else{
                return nums2[(m-1)/2];
            }
        }

        //此时没有为空的
        int i=0,j=0;
        int count=0;
        while(count!=m+n){
            //第一个数组处理完了,那就是把第二个数组放进去就行了
            if(i==m){
                while (j!=n){
                    nums[count++]=nums2[j++];
                }
                break;
            }

            //第二个数组处理完了，那就是把第一个数组放进去就行了
            if(j==n){
                while (i!=m){
                    nums[count++]=nums2[j++];
                }
                break;
            }

            if(nums1[i]<nums2[j]){
                nums[count++]=nums1[i++];
            }else{
                nums[count++]=nums1[j++];
            }

        }

        if (count % 2 == 0) {
            return (nums[count / 2 - 1] + nums[count / 2]) / 2.0;
        } else {
            return nums[count / 2];
        }

    }

    /**
     * 用 len 表示合并后数组的长度，如果是奇数，我们需要知道第 （len + 1）/ 2 个数就可以了，如果遍历的话需要遍历 int ( len / 2 ) + 1 次。
     * 如果是偶数，我们需要知道第 len / 2 和 len / 2 + 1 个数，也是需要遍历 len / 2 + 1 次。所以遍历的话，奇数和偶数都是 len / 2 + 1 次。
     * @param nums1
     * @param nums2
     * @return
     */
    private static double findMedianSortedArrays2(int[] nums1, int[] nums2) {
        int m=nums1.length;
        int n=nums2.length;
        int len=m+n;
        int left=-1,right=-1;
        //数组起始点
        int aStart = 0, bStart = 0;

        for(int i=0;i<=len/2;i++){
            left=right;
            if(aStart<m && (bStart>=n || nums1[aStart]<nums2[bStart])){
                right=nums1[aStart++];
            }else{
                right=nums2[bStart++];
            }
        }

        if(len%2==0){
            return left+right;
        }else{
            return right;
        }

    }







}
